package org.example.myleet.presum;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class PresumSolution {

    /**
     * 304【前缀和】二维区域和检索 - 矩阵不可变
     */
    static class NumMatrix {
        private int m;
        private int n;
        private long[][] diffMatrix;
        /**
         * 14 ms
         *  ----------------------
         * ｜             |       ｜
         * ｜             |       ｜
         * ｜    重叠      |  横向 ｜
         * ｜             |       ｜
         * ｜ ------------------- ｜
         * ｜             |       ｜
         * ｜    纵向      | 结果  ｜
         *  ----------------------
         * 前缀和矩阵，用矩形内部分成3块的方式计算最右下角那块的和
         */
        public NumMatrix(int[][] matrix) {
            m = matrix.length;
            if (m > 0) {
                n = matrix[0].length;
                diffMatrix = new long[m][n];
                diffMatrix[0][0] = matrix[0][0];
                //先初始化第一列和第一行
                for (int i = 1; i < m; i++) {
                    diffMatrix[i][0] = diffMatrix[i - 1][0] + matrix[i][0];
                }
                for (int j = 1; j < n; j++) {
                    diffMatrix[0][j] = diffMatrix[0][j - 1] + matrix[0][j];
                }
                //然后初始化矩阵剩余部分
                for (int i = 1; i < m; i++) {
                    for (int j = 1; j < n; j++) {
                        //前缀和矩阵的每个位置都是横向矩形加纵向矩形，减去重叠部分，加上matrix相应位置的值得到
                        diffMatrix[i][j] = diffMatrix[i][j - 1] + diffMatrix[i - 1][j] - diffMatrix[i - 1][j - 1] + matrix[i][j];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if (m == 0 || n == 0) {
                return 0;
            }
            //将矩形分割成三份，结果是右下角的那块，需要用总面积减去横向的子矩形和纵向的子矩形，由于多减了重叠部分，所以需要加回重叠部分
            return (int) (diffMatrix[row2][col2] - (row1 > 0 ? diffMatrix[row1-1][col2] : 0) - (col1 > 0 ? diffMatrix[row2][col1-1] : 0) + (row1 > 0 && col1 > 0 ? diffMatrix[row1-1][col1-1] : 0));
        }
    }

    //p813
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] preSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        double[][] dp = new double[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = preSum[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j - 1; x < i; x++) {
                    dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (preSum[i] - preSum[x]) / (i - x));
                }
            }
        }
        return dp[n][k];
    }

    //p1124
    public int longestWPI(int[] hours) {
        int n = hours.length;
        int[] preSum = new int[n + 1];
        Map<Integer, Integer> preSumFirstAppearance = new HashMap<>();
        preSumFirstAppearance.put(0, 0);
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + (hours[i] > 8 ? 1 : -1);
            preSumFirstAppearance.putIfAbsent(preSum[i + 1], i + 1);
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (preSum[i] > 0) {
                max = Math.max(max, i);
            } else {
                Integer j = preSumFirstAppearance.get(preSum[i] - 1);
                if (null != j && j < i) {
                    max = Math.max(max, i - j);
                }
            }
        }
        return max;
    }

    //p1744
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        long[] preSum = new long[candiesCount.length + 1];
        preSum[0] = 0;
        preSum[1] = candiesCount[0];
        for (int i = 1; i < candiesCount.length; ++i) {
            preSum[i + 1] = preSum[i] + candiesCount[i];
        }
        boolean[] result = new boolean[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int candyType = queries[i][0];
            long leastCandy = preSum[candyType];
            long maxCandy = preSum[candyType + 1];
            if (((long) (queries[i][1] + 1) * queries[i][2]) > leastCandy) {
                if ((queries[i][1] + 1) <= maxCandy) {
                    result[i] = true;
                }
            }
        }
        return result;
    }

    //p1894
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        //前缀和，注意int的溢出
        long total = chalk[0];
        for (int i = 1; i < n; ++i) {
            total += chalk[i];
        }
        k = (int) (k % total);
        for (int i = 0; i < n; ++i) {
            if (k < chalk[i]) {
                return i;
            }
            k -= chalk[i];
        }
        return -1;
    }

    //p2055
    public int[] platesBetweenCandles(String s, int[][] queries) {
        char[] charArr = s.toCharArray();
        //记录每个位置上的左侧碟子数量，只在是蜡烛的位置才记录左侧碟子数量
        int[] candleLeftPlateCount = new int[charArr.length + 1];
        //记录每个位置上左侧最近的蜡烛位置
        int[] nearestLeftCandleIndexes = new int[charArr.length];
        int leftCandleIndex = -1;
        //记录每个位置上右侧最近的蜡烛位置
        int[] nearestRightCandleIndexes = new int[charArr.length];
        int rightCandleIndex = -1;
        //碟子数量
        int plateCount = 0;
        for (int i = 0; i < charArr.length; ++i) {
            if (charArr[i] == '|') {
                //如果是蜡烛，记录左侧最近的蜡烛
                leftCandleIndex = i;
                candleLeftPlateCount[i] = plateCount;
            } else {
                //condition of '*'(plate)
                ++plateCount;
            }
            nearestLeftCandleIndexes[i] = leftCandleIndex;
        }
        for (int i = charArr.length - 1; i >= 0; --i) {
            if (charArr[i] == '|') {
                //如果是蜡烛，记录右侧最近的蜡烛
                rightCandleIndex = i;
            }
            nearestRightCandleIndexes[i] = rightCandleIndex;
        }
        int[] result = new int[queries.length];
        if (plateCount == charArr.length) {
            //碟子数量等于字符数量，相当于完全没有蜡烛，后面就不用查询了，因为所有查询两根蜡烛之间碟子数结果都为0
            return result;
        }
        for (int i = 0; i < queries.length; ++i) {
            //找到queries[i][0]的右侧最近蜡烛和queries[i][1]的左侧最近蜡烛，中间的碟子数量通过前缀和的方式计算出来
            int leftCandle = nearestRightCandleIndexes[queries[i][0]];
            int rightCandle = nearestLeftCandleIndexes[queries[i][1]];
            if (leftCandle >= 0 && rightCandle >= 0 && leftCandle < rightCandle) {
                result[i] = candleLeftPlateCount[rightCandle] - candleLeftPlateCount[leftCandle];
            }
        }
        return result;
    }

    //2389
    public int[] answerQueries(int[] nums, int[] queries) {
        int n = nums.length, m = queries.length;
        Arrays.sort(nums);
        int[] cq = new int[queries.length];
        System.arraycopy(queries, 0, cq, 0, m);
        Arrays.sort(cq);
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        Map<Integer, Integer> qMapLen = new HashMap<>();
        int r = 0, i = 0;
        while (r <= n && i < m) {
            if (qMapLen.containsKey(cq[i])) {
                ++i;
                continue;
            }
            int p = preSum[r], pNext = r == n ? preSum[n] : preSum[r + 1];
            if (p <= cq[i]) {
                if (pNext > cq[i]) {
                    qMapLen.put(cq[i], r);
                    ++i;
                } else {
                    ++r;
                }
            } else {
                qMapLen.put(cq[i], r);
                ++i;
            }
        }
        if (i < m) {
            for (; i < m; ++i) {
                qMapLen.put(cq[i], n);
            }
        }
        int[] answer = new int[m];
        for (i = 0; i < m; ++i) {
            answer[i] = qMapLen.get(queries[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        double epsilon = 0.00001;
        PresumSolution solution = new PresumSolution();
        Assert.isTrue(20.0 == solution.largestSumOfAverages(new int[]{9,1,2,3,9}, 3));
        Assert.isTrue(20.5 == solution.largestSumOfAverages(new int[]{1,2,3,4,5,6,7}, 4));
        Assert.isTrue(Math.abs(18.16667 - solution.largestSumOfAverages(new int[]{4,1,7,5,6,2,3}, 4)) < epsilon);

        Assert.isTrue(3 == solution.longestWPI(new int[]{9,9,9}));
        Assert.isTrue(9 == solution.longestWPI(new int[]{9,9,6,0,6,6,9,9,9}));
        Assert.isTrue(3 == solution.longestWPI(new int[]{9,9,6,0,6,6,9}));
        Assert.isTrue(0 == solution.longestWPI(new int[]{6,6,6}));

        Assert.isTrue("[2,2,1,1,2,3,3]".equals(JsonUtils.toJson(solution.answerQueries(new int[]{736411,184882,914641,37925,214915}, new int[]{331244,273144,118983,118252,305688,718089,665450}))));
        Assert.isTrue("[2,3,4]".equals(JsonUtils.toJson(solution.answerQueries(new int[]{4,5,2,1}, new int[]{3,10,21}))));
    }
}
